package com.basic.kmp;

/**
 * KMP.. 算法
 *
 * https://blog.csdn.net/yutong5818/article/details/81319120
 * https://segmentfault.com/a/1190000008575379 // 优化不看不懂
 *
 * @author Lizhong
 * @date 2019/10/15
 */
public class KMP {
    /**
     * ABAC
     * next[0]=0 ，0,1,0,0
     * next[0]=-1, 0,0,0,1
     * @param s
     * @return
     */
    static int[] getNext(String s) {
        int[] next = new int[s.length()];
        next[0] = 0;
        for (int i = 1, k = 0; i < s.length(); i++) {
            // 考虑k>0
            while (k > 0 && s.charAt(i) != s.charAt(k))
                k = next[k - 1];
            // 若想等+1
            if (s.charAt(i) == s.charAt(k))
                k++;
            next[i] = k;
        }
        return next;
    }

    static int kmp(String s, String t) {
        int[] next = getNext(t);
        int j = 0;
        for (int i = 0; i < s.length(); i++) {
            // j=0开始，根据next数组性质移动前一位的next长度
            while (j > 0 && t.charAt(j) != s.charAt(i)) {
                j = next[j - 1];
            }
            if (t.charAt(j) == s.charAt(i)) j++;
            // 下标建长度+1， 1234  23 下标2-2+1=1
            if (j >= t.length()) return i - t.length() + 1;

        }
        return -1;

    }

    public static void main(String[] args) {
        String s = "1234761123458412";
        String t = "12345";
        int kmp = kmp(s, t);
        System.out.println(kmp);
    }
}
